A linked list is simply a chain of structures which contain a pointer to the next element. That is about the simplest explanation I can provide. It is one of the simpler of the advanced data structures, and is frequently one of the first things a student learns in a second year university level data structures course. Here is a diagram to illustrate what I mean:

This definition applies only to Singly Linked Lists - Doubly Linked Lists, Skip Lists and Circle Lists are different.

Some common examples of a linked list:

• The AmigaDOS Viewport structure always points to the next viewport. You can have multiple viewports in the same list
• Hash tables use linked lists for collission resolution
• Any "File Requester" dialog uses a linked list
• Binary Trees
• Stacks and Queues can be implemented with a doubly linked list
• Relational Databases (EG Microsoft Access)

And the list goes on ...

How to address elements in a linked list

It is always a good idea to put your linked list into it's own Class. This makes it much easier to manage as you can write your own methods to manipulate it. A linked list class should contain the following elementary functions:

• Add To Head (Var_Type element)
• Add To Tail (Var_Type element)
• Var_Type Remove From Head
• Var_Type Remove From Tail

A list item has a pointer to the next element, or to 0 if the current element is the tail (end of the list). This pointer is of the same type as the structure itself. This structure that contains elements and pointers to the next structure is called a Node. A sample call would look like the following:

	//move to the next element in the list
	temp = temp->next;

	//move 2 elements down the list
	temp = temp->next->next; // and so on

	//go to the head of the list
	temp = head; // temp = tail to go to the end

These 3 examples show how easy it is to traverse a list. As you move though the list, to access the elements all you need to do is address the appropriate feild in the Node structure.

	value = Node->info;
	// info is the data contained at this location in the list

Elementary Linked List Functions

I have created a set of elementary function that should be included in all linked lists. These functions allow the user to add or remove elements to the linked list. In this example, the datatype I am going to use is undefined. Depending on the language you wish to use for actual implemenation, you can use virtually any datatype (even a linked list itself!)

Adding an element to the head of a linked list

Adding an element to the head of a linked list is quite simple. First the procedure must allocate the appropriate resources/memory in such a way that it will point to the head of the list. Then it will make sure that current element (head+1 if you will) is not the last element in the list. If so, it will change the pointers accordingly.

	// Add an element to the start of the linked list
	procedure AddToHead(element)
		head = new Node(element, head)
		if(not the Tail)
			tail = head
		end if
	end procedure

Adding an element to the tail of a linked list

Adding an element to the tail of a list is slightly different. The procedure must allocate a node that is pointed to by the last element in the list. Then the procedure must set the current node pointer to the next element, and do the same for the tail pointer (tail+1 if you will).

	// Add an element to the tail of the linked list
	procedure AddToTail(element)
		if(this is the Tail)
			tail->next = new Node(el)
			tail = tail->next
		endif
		else head = tail = new Node(el)
	end procedure

Removing an element from the head of a linked list

This one is a little harder to follow. First, it must get the element contained in head. Then it must patch up the linked list accordingly. The bond between head and the next element is broken, so the next element in the list is set to be the head.

	// Remove an element from the head of the linked list
	procedure RemoveFromHead():integer
		if(this is the Head)
			element = head->info
			temp = head
			if(this is the last item in the list)
				Break pointer connection between head and tail to terminate list
			else
				set head.next to equal next item in list
			end if
			release temp from from memory pool
			return element
		else
			return 0
		end if
	end procedure

Removing an element from the head of a linked list

Removing an element from the tail of the list is a bit simpler. First, the element must be obtained, then the memory used by the tail node is released. The tail pointer is set at the preceeding element and the procedure makes sure that this is not the last element in the list.

	// Remove an element from the tail of the linked list
	procedure RemoveFromTail():integer
		if(this is the Tail)
			element = tail->info
			if(this is the last item in the list)
				Break pointer connection between head and tail to terminate list
				release head from memory pool
			else
				Traverse list until you reach the tail
				release tail from memory pool
				set tail pointer to previous element if one exists
				set tail's pointer to next element to null
			end if
			return element
		else
			return 0
		end if
	end procedure

Conclusion

Singly linked lists are useful data structures, especially if you need to automatically allocate and de-allocate space in a list. The code and complexity of these algorithms is bigger, but the tradeoff is ease of use. As far as complexity is concerned, a linked list should never exceed O(n²). If you are very lucky, linear time can be acheived (only under several conditions, such as there being only 1 item in the list, or the current element pointed at is the head or the tail). Sorting linked lists can be a chore, but with careful selection of sorting algorithms, nearly constant time can be acheived. Counting Sort works the best for integers, and Quicksort works great for non-integer items (such as floats).

Download Linked List Class

This list class is written in C++. It has been tested with Storm C++ and Microsoft Visual C++ 4.1. It worked fine with both.

Download linklist.cpp